package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class Ex1_4_44 {

   //  Math.sqrt(N*3.14/2)
    public static void main(String[] args) {
        int N=500;
        StdOut.println("平均次数："+Math.sqrt(Math.PI*N/2));

        for (int times=0;times<100;times++) {
            boolean contains=false;
            RandomTest randomTest=new RandomTest(N);
            for (int i = 0; i < 500&& !contains; i++) {
                randomTest.random();
                if (randomTest.contains()) {
                    StdOut.println("出现了重复，次数" + (i + 1));
                    contains=true;
                }
            }
        }
    }

    private static class RandomTest{
        private int hi;
        private int lo;
        private int[] a;
        private int pos;
        public RandomTest(int N){
            lo=0;
            hi=N-1;
            a=new int[N];
        }
        public int random(){
            int r=StdRandom.uniform(lo,hi);
            a[pos++]=r;
            return r;
        }

        public boolean contains(){
            for (int i=0;i<pos;i++){
                for (int j=i+1;j<pos;j++){
                    if (a[i]==a[j]){
                        return true;
                    }
                }
            }
            return false;
        }
    }
}
